package top.hkyzf.study.leetcode.bit;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-2-28 9:05
 */
public class 最多可达成的换楼请求数目_1601 {
    int[][] rs;

    public int maximumRequests(int n, int[][] requests) {
        rs = requests;
        int m = rs.length;
        int ans = 0;
        for (int i = 0; i < (1 << m); i++) {
            int cnt = getCnt(i);
            if (cnt <= ans) {
                continue;
            }
            if (check(i)) {
                ans = cnt;
            }
        }
        return ans;
    }

    boolean check(int s) {
        int[] cnt = new int[20];
        int sum = 0;
        for (int i = 0; i < 16; i++) {
            if (((s >> i) & 1) == 1) {
                int a = rs[i][0];
                int b = rs[i][1];
                if (++cnt[a] == 1) {
                    sum++;
                }
                if (--cnt[b] == 0) {
                    sum--;
                }
            }
        }
        return sum == 0;
    }

    int getCnt(int s) {
        int ans = 0;
        for (int i = s; i > 0; i = i - (i & -i)) {
            ans++;
        }
        return ans;
    }

    @Test
    public void testMaximumRequests () {
        // 没做出来，看的答案
        int n = 5;
        int[][] requests = {{0,1},{1,0},{0,1},{1,2},{2,0},{3,4}};
        System.out.println(maximumRequests(n, requests));
    }
}
